package pers.sloera.leetcode.editor.cn;//给你一个有 n 个服务器的计算机网络，服务器编号为 0 到 n - 1 。同时给你一个二维整数数组 edges ，其中 edges[i] = [ui,
//vi] 表示服务器 ui 和 vi 之间有一条信息线路，在 一秒 内它们之间可以传输 任意 数目的信息。再给你一个长度为 n 且下标从 0 开始的整数数组 
//patience 。 
//
// 题目保证所有服务器都是 相通 的，也就是说一个信息从任意服务器出发，都可以通过这些信息线路直接或间接地到达任何其他服务器。 
//
// 编号为 0 的服务器是 主 服务器，其他服务器为 数据 服务器。每个数据服务器都要向主服务器发送信息，并等待回复。信息在服务器之间按 最优 线路传输，也就
//是说每个信息都会以 最少时间 到达主服务器。主服务器会处理 所有 新到达的信息并 立即 按照每条信息来时的路线 反方向 发送回复信息。 
//
// 在 0 秒的开始，所有数据服务器都会发送各自需要处理的信息。从第 1 秒开始，每 一秒最 开始 时，每个数据服务器都会检查它是否收到了主服务器的回复信息（
//包括新发出信息的回复信息）： 
//
// 
// 如果还没收到任何回复信息，那么该服务器会周期性 重发 信息。数据服务器 i 每 patience[i] 秒都会重发一条信息，也就是说，数据服务器 i 在上
//一次发送信息给主服务器后的 patience[i] 秒 后 会重发一条信息给主服务器。 
// 否则，该数据服务器 不会重发 信息。 
// 
//
// 当没有任何信息在线路上传输或者到达某服务器时，该计算机网络变为 空闲 状态。 
//
// 请返回计算机网络变为 空闲 状态的 最早秒数 。 
//
// 
//
// 示例 1： 
//
// 
//
// 输入：edges = [[0,1],[1,2]], patience = [0,2,1]
//输出：8
//解释：
//0 秒最开始时，
//- 数据服务器 1 给主服务器发出信息（用 1A 表示）。
//- 数据服务器 2 给主服务器发出信息（用 2A 表示）。
//
//1 秒时，
//- 信息 1A 到达主服务器，主服务器立刻处理信息 1A 并发出 1A 的回复信息。
//- 数据服务器 1 还没收到任何回复。距离上次发出信息过去了 1 秒（1 < patience[1] = 2），所以不会重发信息。
//- 数据服务器 2 还没收到任何回复。距离上次发出信息过去了 1 秒（1 == patience[2] = 1），所以它重发一条信息（用 2B 表示）。
//
//2 秒时，
//- 回复信息 1A 到达服务器 1 ，服务器 1 不会再重发信息。
//- 信息 2A 到达主服务器，主服务器立刻处理信息 2A 并发出 2A 的回复信息。
//- 服务器 2 重发一条信息（用 2C 表示）。
//...
//4 秒时，
//- 回复信息 2A 到达服务器 2 ，服务器 2 不会再重发信息。
//...
//7 秒时，回复信息 2D 到达服务器 2 。
//
//从第 8 秒开始，不再有任何信息在服务器之间传输，也不再有信息到达服务器。
//所以第 8 秒是网络变空闲的最早时刻。
// 
//
// 示例 2： 
//
// 
//
// 输入：edges = [[0,1],[0,2],[1,2]], patience = [0,10,10]
//输出：3
//解释：数据服务器 1 和 2 第 2 秒初收到回复信息。
//从第 3 秒开始，网络变空闲。
// 
//
// 
//
// 提示： 
//
// 
// n == patience.length 
// 2 <= n <= 10⁵ 
// patience[0] == 0 
// 对于 1 <= i < n ，满足 1 <= patience[i] <= 10⁵ 
// 1 <= edges.length <= min(10⁵, n * (n - 1) / 2) 
// edges[i].length == 2 
// 0 <= ui, vi < n 
// ui != vi 
// 不会有重边。 
// 每个服务器都直接或间接与别的服务器相连。 
// 
// Related Topics 广度优先搜索 图 数组 👍 42 👎 0


import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution2039 {
    // public static void main(String[] args) {
    //   final Solution solution = new Solution();
    //   int[] patience = new int[]{0, 10, 10};
    //   int[][] edges = new int[][]{{0, 1}, {0, 2}, {1, 2}};
    //   final int i = solution.networkBecomesIdle(edges, patience);
    //   System.out.println(i);
    // }

    /**
     * <ul>
     *   <li>先求出图中任意节点之间的最短距离</li>
     *   <li>再求出每个节点变为空闲的时间</li>
     * </ul>
     *
     * <p>求空闲时间：节点v与节点0之间的最短距离为dist，当节点v接收到主服务器节点0的最后一个回复后的下一秒，节点v变为空闲</p>
     * <ul>
     *   <li>节点v发送一个消息经过dist秒到达节点0</li>
     *   <li>节点0回复消息经过dist秒到达节点v</li>
     *   <li>节点v每发送一次消息，经过2 * dist 秒收到回复</li>
     *   <li>节点v发送消息的周期为patience[v]</li>
     *   <ul>
     *     <li>当2*dist <= patience[v]时：节点v只会发送一次消息，此时节点v变为空闲的时间为2 * dist + 1</li>
     *     <li>当2*dist > patience[v]时：在[1, 2*dist)时间范围内会再次发送 (2*dist-1)/patience[v] 次消息，最后一次发送消息的时间为 patience[v] * ((2*dist-1)/patience[v])， 最后一次收到回复的时间为 patience[v] * ((2*dist-1)/patience[v]) + 2 * dist，变为空闲的时间为 patience[v] * ((2*dist-1)/patience[v]) + 2 * dist + 1</li>
     *   </ul>
     * </ul>
     *
     * @return int
     * @date 2022/3/20
     */
    public int networkBecomesIdle(int[][] edges, int[] patience) {
        final int n = patience.length;
        boolean[] visit = new boolean[n];
        // final HashMap<Integer, ArrayList<Integer>> adjacency = new HashMap<>();
        List<Integer>[] adjacency = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adjacency[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            // 路径存储相连接的节点
            // 无向， 两边都可达
            adjacency[edge[0]].add(edge[1]);
            adjacency[edge[1]].add(edge[0]);
        }
        // 初始化结束
        // 广度优先
        final ArrayDeque<Integer> queue = new ArrayDeque<>();
        // 节点0 的距离为1
        int earliestSecond = 0;
        int dist = 1;
        visit[0] = true;
        // BFS
        queue.offer(0);
        while (!queue.isEmpty()) {
            // size 会变
            final int size = queue.size();
            for (int i = 0; i < size; i++) {
                for (Integer nextNode : adjacency[queue.poll()]) {
                    if (visit[nextNode]) {
                        continue;
                    }
                    // push 添加到队首 不可以
                    // queue.push(nextNode);
                    queue.offer(nextNode);
                    int time = patience[nextNode] * ((2 * dist - 1) / patience[nextNode]) + 2 * dist + 1;
                    earliestSecond = Math.max(earliestSecond, time);
                    visit[nextNode] = true;
                }
            }
            dist++;
        }
        return earliestSecond;
    }

    public int networkBecomesIdle1(int[][] edges, int[] patience) {
        int n = patience.length;
        List<Integer>[] adj = new List[n];
        for (int i = 0; i < n; ++i) {
            adj[i] = new ArrayList<Integer>();
        }
        boolean[] visit = new boolean[n];
        for (int[] v : edges) {
            adj[v[0]].add(v[1]);
            adj[v[1]].add(v[0]);
        }

        Queue<Integer> queue = new ArrayDeque<Integer>();
        queue.offer(0);
        visit[0] = true;
        int dist = 1;
        int ans = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int curr = queue.poll();
                for (int v : adj[curr]) {
                    if (visit[v]) {
                        continue;
                    }
                    queue.offer(v);
                    int time = patience[v] * ((2 * dist - 1) / patience[v]) + 2 * dist + 1;
                    ans = Math.max(ans, time);
                    visit[v] = true;
                }
            }
            dist++;
        }
        return ans;
    }
}


// 链接：https://leetcode-cn.com/problems/the-time-when-the-network-becomes-idle/solution/wang-luo-kong-xian-de-shi-ke-by-leetcode-qttv/
//leetcode submit region end(Prohibit modification and deletion)
